'''
@Company: TWL
@Author: xue jian
@Email: xuejian@kanzhun.com
@Date: 2020-07-15 09:10:39
'''
'''
96. 不同的二叉搜索树
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
'''
'''
tips:明显的动态规划，状态dp[i]表示i时有多少搜索树。按搜索树要求，如果选取j为根，
则整体分成两部分，大于j与小于j，
这个时候搜索树的个数为dp[j]*dp[i-j-1]。遍历j并相加即可。注意边界，代码相当简单，如下
'''
class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0]*(n+1)
        dp[0] = 1
        for i in range(n+1):
            for j in range(i):
                dp[i] += dp[j]*dp[i-j-1]
        return dp[-1]

if __name__ == "__main__":
    solution = Solution()
    n=4
    print(solution.numTrees(n))